沒想到能撐到現在,今天順便將明後天要介紹的Opening Book跟Endgame Database的大綱先擬好了,事到如今硬著頭皮也得完賽吧。
hackMD原稿
在Day4的時候有提到,對局樹會有很多重複的盤面出現,造成效能的浪費,未來會介紹到Transposition Table就能夠來處理這個問題。
奇異博士看到了上百萬個我棄賽的未來,沒看到的就是今天,我自己都沒想到。
Transposition Table(同形表) 是用來儲存歷史盤面跟相關資訊的,避免在搜尋過程中重複計算已經評估過的棋局狀態。通過儲存已經搜索過的盤面及其相關資訊,當搜索中遇到相同的盤面時,直接從使用之前的結果,從而節省計算資源和時間。
再看一次上下兩條分支,雖然過程不同,但結果相同的情況。
再來就是這種旋轉跟鏡像對稱的盤面,其實都可以視為同一種。
在搜索的過程中,如果先把分支的結果給存下來,只要遇到重複的盤面就直接使用之前搜索過的結果,這樣就可以省去不必要的重複計算。
如下圖,本來 X 下在中間後,O 有8種下法,但實際上我們只需要搜索其中的2種,剩下的盤面都可以直接查詢歷史盤面,不用再重新搜索了。
初始盤面也是只需要搜索其中的3種,比前面介紹的所有剪枝都還要強大。
Transposition Table也可以用來處理循環走步的問題。
圍棋
黑棋可以在A點將白棋給吃掉。
但就在黑棋提過去之後 A 點的棋子也只剩下一氣,白棋如果下在 B 點也可以把黑棋吃掉。
這樣雙方只要開始提來提去那這盤棋就沒完沒了了,所以圍棋有個規則是,當對方提過來時,我方必須隔一手之後才能提回去,這就是打劫。
這邊就可以檢查歷史盤面,來檢查是否有違規情況,比如上圖中黑棋下在 A 點將白棋吃掉後,白棋不能夠馬上於 B 點吃回去,必須先在其他地方落子,下一個回合後才能夠吃回來,如果白棋馬上吃回去,那就會跟歷史盤面有重複,所以只要有重複盤面就可以判定是違規。
(三劫、四劫、長生劫等複雜循環行為這裡暫時不去探討)
象棋
長將、長捉、長殺(棋例)
西洋棋
三次重複
其他還有像是跳棋、Surakarta,都是很容易發生循環走步的遊戲,設計一個好的Transposition Table就會變得非常重要。
一開始在看井字遊戲大家可能不會有感覺,但是看一下象棋、西洋棋或是圍棋,要如何存下過往盤面資訊?
如果是用Array來表示棋盤資料結構的話,然後將每個盤面的Array都儲存下來,就算不考慮比對Array的效能。
圍棋隨便都能達到上百手,你在每個盤面展開的時候都得去比對前面一百個盤面,這樣線性搜索效能肯定是非常差的,這時候我們就會用到Hash。
圖片擷取自how programmers overprepare for job interviews,這影片太好笑了一定要點進去看!
而Zobrist Hashing應該是目前最常見的建同形表的方式,Day16也有提到過一個Zobrist's Model,沒錯!這兩個Zobrist是同一位,就是Albert Zobrist。
Zobrist Hashing 通過給每個棋子在每個位置上分配一個隨機的二進制數字(hash值),來表示盤面。當棋子移動時,可以使用位元運算快速更新整個棋盤的hash值,而不必重新計算整個盤面的hash值。
正常情況你得給新的盤面一個新的hash值,但Zobrist Hashing只針對移動的棋子做XOR,效率會高非常多。
以西洋棋為例,步驟如下:
步驟1可以一開始就產生好,不用每次遊戲都產生一個新的隨機數表,比如在Deep Learning and the Game of Go這個開源程式中,他已經先建立好一個HASH_CODE,實際的操作範例可以看goboard_fast.py。
詳細XOR的特性與證明請至邏輯互斥或查看。
因為這兩個特性,XOR不會被順序影響,無論棋子移動順序如何,結果hash值一致。
Transposition Table對於對局樹的搜索來說相當重要,可能你費盡心思做了一大堆剪枝,都不如實作一個Transposition Table,對效能的影響非常的大。使用Zobrist Hashing可以用相對小的空間儲存各種棋盤狀態,並且能利用位元運算XOR快速更新,現在就為你的程式實作一個吧!
本來還想寫一點當Transposition Table滿了之後的一些置換策略,但想到現在的記憶體隨便都16G、32G,還非常便宜,就不用考慮Transposition Table的大小了吧。